package com.lsa.letcode.the140.wordBreakII;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        return doSegment2(s, dict);
    }
    
    private List<String> doSegment2(String s, Set<String> dict) {
    	if (s == null || s.isEmpty()) {
    		return new ArrayList<String>();
    	}
    	// dp[i]=true means s[0,i] canBeSegmented
    	@SuppressWarnings("unchecked")
		List<String>[] dp = new List[s.length()];
    	for (int i = 0; i < dp.length; i++) {
			dp[i] = new ArrayList<String>();
		}
    	
    	{
    		String substr = s.substring(0, 1);
			if (dict.contains(substr)) {
    			dp[0].add(substr);
    		}
    	}
    	for (int i = 1; i < dp.length; i++) {
    		// check [0, i]
    		// [0, i]=true, 
    		// 		if 
    		//			[0,i] in dict
    		//			OR
    		//	 		$EXIST$ j in [0,i-1], s.t.  [0, j]=true AND [j+1, i] in dict.
    		//		
    		if (dict.contains(s.substring(0, i+1))) {
    			dp[i].add(s.substring(0, i+1));
    		}
    		
    		for (int j = 0; j < i; j++) {
				String substr = s.substring(j + 1, i + 1);
				if (!dp[j].isEmpty() && dict.contains(substr)) {
					dp[i].add(substr);
				}
			}
		}
    	
    	List<String> words = getWords2(dp, dp.length - 1);
    	Collections.sort(words, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				return o2.compareTo(o1);
			}
		});
		return !dp[s.length() - 1].isEmpty()? words : new ArrayList<String>();
    }
    
    private List<String> getWords2(List<String>[] dp, int idx) {
    	List<String> words = new ArrayList<String>();
    	if (idx < 0){
    		return words;
    	}
    	// check [0, i]
		// [0, i]=true, 
		// 		if 
		//			[0,i] in dict
		//			OR
		//	 		$EXIST$ j in [0,i-1], s.t.  [0, j]=true AND [j+1, i] in dict.
		//		
    	for (String w : dp[idx]) {
    		List<String> subWords = getWords2(dp, idx - w.length());
    		for (String sw : subWords) {
    			words.add(sw + " " + w);
			}
    		if (subWords.isEmpty()) {
    			words.add(w);
    		}
			
		}
		return words;
	}
    
    @SuppressWarnings("unused")
	private List<String> doSegment(String s, Set<String> dict) {
    	if (s == null || s.isEmpty()) {
    		return new ArrayList<String>();
    	}
    	// dp[i]=true means s[0,i] canBeSegmented
    	boolean[] dp = new boolean[s.length()];
    	
    	@SuppressWarnings("unchecked")
		List<DpSolution>[] dpSolutions = new List[s.length()];
    	for (int i = 0; i < dpSolutions.length; i++) {
    		dpSolutions[i] = new ArrayList<DpSolution>();
		}
    	
    	dp[0] = dict.contains(s.substring(0, 1));
    	if (dp[0]) {
    		dpSolutions[0].add(new DpSolution(0, 0));
    	}
    	for (int i = 1; i < dp.length; i++) {
    		// check [0, i]
    		// [0, i]=true, 
    		// 		if 
    		//			[0,i] in dict
    		//			OR
    		//	 		$EXIST$ j in [0,i-1], s.t.  [0, j]=true AND [j+1, i] in dict.
    		//		
    		if (dict.contains(s.substring(0, i+1))) {
    			dp[i] = true;
    			dpSolutions[i].add(new DpSolution(0, i));
    		}
    		
    		for (int j = 0; j < i; j++) {
				if (dp[j] && dict.contains(s.substring(j + 1, i + 1))) {
					dp[i] = true;
					dpSolutions[i].add(new DpSolution(j, j + 1, i));
				}
			}
		}
    	
    	List<String> words = getWords(s, dpSolutions);
    	Collections.sort(words, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				return o2.compareTo(o1);
			}
		});
		return dp[s.length() - 1]? words : new ArrayList<String>();
    }
    
    private static List<String> getWords(String str, List<DpSolution>[] allSolutions) {
    	List<String> words = new ArrayList<String>();
    	for (DpSolution s : allSolutions[allSolutions.length - 1]) {
    		words.addAll(getWords(str, allSolutions, s));
		}
    	return words;
    }

	private static List<String> getWords(String str, List<DpSolution>[] allSolutions, DpSolution sol) {
    	if (sol.parent == -1) {
    		return Arrays.asList(str.substring(sol.from, sol.to + 1));
    	}
    	else {
    		String inDictStr = str.substring(sol.from, sol.to + 1);
    		List<DpSolution> sols = allSolutions[sol.parent];
    		List<String> words = new ArrayList<String>();
    		for (DpSolution subSol : sols) {
    			List<String> subSolWords = getWords(str, allSolutions, subSol);
    			for (String w : subSolWords) {
    				words.add(w + " " + inDictStr);
				}
			}
    		return words;
    	}
    }
    
    static class DpSolution {
    	int parent; // -1 or parent
    	
    	// s[from, to] in dict
    	int from;
    	int to;
    	
		DpSolution(int from, int to) {
			parent = -1;
			this.from = from;
			this.to = to;
		}

		DpSolution(int parent, int from, int to) {
			this.parent = parent;
			this.from = from;
			this.to = to;
		}
    }
}